﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace TheStar.Lib
{
    public class BranchAndBound
    {
        private readonly SortedLinkedList<Path> list;
        private readonly IProblemGraph problem;

        public BranchAndBound(IProblemGraph problem)
        {
            if (problem == null)
            {
                throw new ArgumentNullException("problem");
            }
            this.problem = problem;
            this.list = new SortedLinkedList<Path>();
            this.list.Add(this.NewPath(problem.First));
        }

        public bool IsEmpty
        {
            get { return this.list.Count == 0; }
        }
        private Path First
        {
            get
            {
                if (this.IsEmpty)
                {
                    return null;
                }
                else
                {
                    Path first = this.list.First.Value;
                    this.list.Remove(first);
                    return first;
                }
            }
        }

        public virtual Path Run()
        {
            Path path = null;
            while (!this.IsEmpty && !(path = this.First).Last.Equals(this.problem.Destination))
            {
                foreach (Transition tran in this.problem.GetChildren(path.Last))
                {
                    if (!path.HasNode(tran.Child))
                    {
                        Path newPath = (Path)path.Clone();
                        newPath.Add(tran.Child, tran.Cost);

                        this.SetAditionalCost(newPath);

                        this.Add(newPath);
                    }
                }
                path = null;
            }
            if (path != null)
            {
                return path;
            }
            else
            {
                return null;
            }
        }
        protected virtual Path NewPath(object node)
        {
            return new Path(node);
        }
        protected virtual void SetAditionalCost(Path path) { }
        protected virtual void Add(Path path)
        {
            this.list.Add(path);
        }
        protected virtual void Remove(Path path)
        {
            this.list.Remove(path);
        }
    }
}
